The present invention relates to a technique for ensuring security of confidential information.
Cryptographic processing apparatuses proposed so far employ a block cipher or a stream cipher for concealing data. Various types of block ciphers have been proposed including DES and IDEA. DES and IDEA are described in the following reference.
Reference 1: Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp. 250–259, pp. 263–266.
The security of the total cryptographic process of each block cipher and its characteristics are discussed based on a block-cipher operation mode employed, such as ECB, CBC, CFB, OFB, or the counter mode. However, only the iaPCBC mode is known to be capable of performing both cryptographic processing and detection of an alteration at the same time, and other modes cannot detect alterations by themselves. Block-cipher operation modes are described in the following reference.
Reference 2: Schneider, Applied Cryptography, Second Edition, John Wiley & Sons, Inc., 1996, pp. 189–209.
The iaPCBC mode is described in the following reference.
Reference 3: Gligor, Donescu, “Integrity-Aware PCBC Encryption Schemes,” Preproceedings in Secure Protocol Workshop, Cambridge, 1999, to appear in Lecture Notes in Computer Science series, Springer-Verlag.
The iaPCBC mode is an operation mode which uses a block cipher. Regarding encryption, the iaPCBC mode can perform neither parallel processing nor preprocessing, which makes it very difficult to implement the iaPCBC mode in the environment in which processing at extremely high speed is required.
On the other hand, there is a system which generates a cryptographic checksum called a “message authentication code” (hereinafter referred to as “MAC”) in order to detect alterations. By implementing a MAC generation process as an independent mechanism, and executing the process during cryptographic processing in one of the above block-cipher operation modes, it is possible to perform both cryptographic processing and detection of an alteration at the same time. In this case, however, it is necessary to share two completely independent cryptographic keys, one for encryption and the other for alteration detection, and, furthermore, data to be encrypted must be processed twice, that is, for encryption and for MAC generation. As a result, a realized cryptographic system may be complicated or may not be suitable for processing data having an extended length. In addition, the processing speed of the block cipher is slower than the current communication speed, which means that it is difficult to apply any technique using a combination of the block cipher and MAC to processing of the order of gigabit-per-second or terabit-per-second. MAC is described in the following reference.
Reference 4: Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp. 352–368.
In contrast with the block cipher, a stream cipher is an encryption mechanism which uses one of various proposed cryptographic pseudorandom number generators. The stream cipher was not able to detect alerations by itself regardless of security or characteristics of each implementation. Well-known stream ciphers, or pseudorandom number generators used for stream ciphers include SEAL, a linear feedback shift register using a nonlinear combination generator, a linear feedback shift register using a nonlinear filter, and a clock-controlled linear feedback shift register. SEAL is described in the following reference.
Reference 5: Schneider, Applied Cryptography, Second Edition, John Wiley & Sons, Inc., 1996, pp. 398–400.
On the other hand, systems based on the above feedback shift registers are described in the following reference.
Reference 6: Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp. 203–212.
A technique using a combination of a stream cipher and a MAC can also perform both cryptographic processing and detection of an alteration at the same time, and, furthermore, processing of a stream cipher is 2 to 20 times faster than that of a block cipher. However, as is the case with the combination of a block cipher and MAC, every MAC generation system (meaning every combination of a stream cipher and MAC) requires sharing of two different keys, and processing of a message twice. When considered in detail, the MAC generation system requires a particular mechanism in addition to that necessary for the stream cipher itself, and considerable computational complexity. For example, MAC generation systems such as HMAC and UMAC require a safe hash function having guaranteed cryptographically-collision-free one-way characteristics. This means that it is necessary to implement the above safe function in addition to a stream cipher. HMAC is described in the above Reference 4 (pp. 355, Example 9.67) while UMAC is described in the following reference.
Reference 7: Black, Halevi, Krawczyk, Krovetz, Rogaway, “UMAC: Fast and Secure Message Authentication,” Advances in Cryptology,—CRYPTO '99 Lecture Notes in Computer Science, Vol. 1666, Springer-Verlag, 1999.
Generally, however, hash functions such as SHA-1 and MD5 are very complicated, and are not easy to implement. These hash functions are described in the following reference.
Reference 8: Menezes, van Oorschot, Vanstone, Handbook of Applied Cryptography, CRC Press, 1996, pp. 347–349.
The security of hash functions has not yet been studied adequately in contrast with study of the security of block ciphers. Therefore, a user may not be able to incorporate a hash function because the user cannot rely on the hash function. Of MAC generation systems, MMH uses only a pseudorandom number generator, and requires a very small amount of additional resources such as circuits and programs to add an alteration detection function to the cryptographic process. However, MMH requires a pseudorandom number sequence whose length is as long as that of the message, taking long time to generate necessary random numbers. MMH is described in the following reference.
Reference 9: Halevi, Krawczyk, “MMH: Software Message Authentication in the Gbit/Second Rates,” Fast Software Encryption, 4th International Workshop, FSE '97, Lecture Notes in Computer Science, Vol. 1267, Springer-Verlag, 1997.
As described above, the prior art techniques are unsatisfactory in terms of ensuring of security and high-speed processing, and therefore it is required to develop a safer and faster cryptographic processing technique.